package 二叉搜索树的后序遍历序列;

public class Solution
{
    public boolean VerifySquenceOfBST(int [] sequence)
    {
        if(sequence.length==0||sequence==null)
        {
            return false;
        }
        //末尾元素是根节点，比根节点小的属于左子树，大的属于右子树
        int root=sequence[sequence.length-1];
        //左子树
        int i=0;
        for (; i < sequence.length-1; i++)
        {
            if (sequence[i]>root)
            {
                break;
            }
        }
        //[0,i-1]是左子树，[i,sequence.length-2]是右子树
        //右子树
        for (int k = i; k < sequence.length-1; k++)
        {
            if (sequence[k]<root)
                return false;
        }
        //判断左子树是不是二叉搜索树
        boolean left=true;
        if (i>0)
        {
            int[] leftsequence= new int[i];
            System.arraycopy(sequence,0,leftsequence,0,i);
            left = VerifySquenceOfBST(leftsequence);
        }
        //判断右子树是不是二叉搜索树
        boolean right=true;
        if (i<sequence.length-1)
        {
            int[] rightsequence= new int[sequence.length-i-1];
            System.arraycopy(sequence,i+1,rightsequence,0,sequence.length-i-1);
            right = VerifySquenceOfBST(rightsequence);
        }
        return (left&&right);
    }

    public static void main(String[] args)
    {
        int[] test={1,2,3,4,5};
        Solution solution = new Solution();
        System.out.println(solution.VerifySquenceOfBST(test));
    }
}
